|
The coin problem (also referred to as the Frobenius coin problem or Frobenius problem, after the mathematician Ferdinand Frobenius) is a mathematical problem that asks for the largest monetary amount that cannot be obtained using only coins of specified denominations. For example, the largest amount that cannot be obtained using only coins of 3 and 5 units is 7 units. The solution to this problem for a given set of coin denominations is called the Frobenius number of the set. There is an explicit formula for the Frobenius number when there are only two different coin denominations. If the number of coin denominations is three or more, no explicit formula is known; but, for any fixed number of coin denominations, there is an algorithm computing the Frobenius number in polynomial time (in the logarithms of the coin denominations forming an input). No known algorithm is polynomial time in the ''number'' of coin denominations, and the general problem, where the number of coin denominations may be as large as desired, is NP-hard. ==Statement== In mathematical terms the problem can be stated: :Given positive integers ''a''1, ''a''2, ..., ''a''''n'' such that gcd(''a''1, ''a''2, ..., ''a''''n'') = 1, find the largest integer that ''cannot'' be expressed as an integer conical combination of these numbers, i.e., as a sum :: ''k''1''a''1 + ''k''2''a''2 + ··· + ''k''''n''''a''''n'', :where ''k''1, ''k''2, ..., ''k''''n'' are non-negative integers. This largest integer is called the Frobenius number of the set , and is usually denoted by ''g''(''a''1, ''a''2, ..., ''a''''n''). The requirement that the greatest common divisor (GCD) equal 1 is necessary in order for the Frobenius number to exist. If the GCD were not 1, every integer that is not a multiple of the GCD would be inexpressible as a linear, let alone conical, combination of the set, and therefore there would not be a largest such number. For example, if you had two types of coins valued at 4 cents and 6 cents, the GCD would equal 2, and there would be no way to combine any number of such coins to produce a sum which was an odd number. On the other hand, whenever the GCD equals 1, the set of integers that cannot be expressed as a conical combination of is bounded according to Schur's theorem, and therefore the Frobenius number exists. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「coin problem」の詳細全文を読む スポンサード リンク
|